package LeetCodeHot100TopInterview;

import java.util.*;

public class Q347_TopKAppear {

    //出现频率 TopK
    //HashMap ==> O(N) + O(N)
    //频率最高 ==> 摩尔投票
    //频率前几高 ==>  ？还是用 Map
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1);
            }
        }
        //数组代替 key - value
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k){
                minHeap.add(new int[]{entry.getKey(), entry.getValue()});
            }else {
                if (entry.getValue() > minHeap.peek()[1]){
                    minHeap.poll();
                    minHeap.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] kArr = new int[minHeap.size()];
        for (int i = kArr.length - 1; i > -1;  i--) {
            kArr[i] = minHeap.poll()[0];
        }
        return kArr;
    }

    public static void main(String[] args) {
        Q347_TopKAppear fun = new Q347_TopKAppear();
        System.out.println(Arrays.toString(fun.topKFrequent(new int[]{4, 1, -1, 2, -1, 2, 3}, 2)));
    }
}
